package 数据结构系列;

import java.util.Deque;
import java.util.LinkedList;

public class 下一个更大元素II_503 {
    public int[] nextGreaterElements(int[] nums) {
        int[] res = new int[nums.length];
        Deque<Integer> stack = new LinkedList<>();
        int n = nums.length;

        //把数组翻倍
        for (int i = 2 * n - 1; i >= 0; i--) {//i=2*n-1：相当于逻辑上把数组扩大一倍，比如原来是{1,2,3}现在就是{1,2,3,1,2,3}

            //原来下标是2，扩大一倍后，还想取到该元素就5%6=5，下标为5，值也是3.用%是为了防止索引越界
            while (!stack.isEmpty() && stack.peek() <= nums[i % n]) {
                stack.pop();//弹出比nums[i]小的元素
            }
            res[i % n] = stack.isEmpty() ? -1 : stack.peek();
            stack.push(nums[i % n]);

        }
        return res;
    }
}
